(1) Field of the Invention
The present invention relates to a navigation system and, more particularly, to a system for detecting the location and orientation of open doorways for autonomous robot exploration.
(2) Discussion of Related Art
Exploration is a fundamental problem for autonomous mobile robots operating in unknown or dynamic environments. Exploration is related to the well-known problem of path planning. However, unlike the original problem, where complete knowledge of the environment is given, exploring an unknown environment is usually performed in a step-by-step greedy fashion. Instead of planning in advance the entire trajectory of the mobile robot, a greedy exploration strategy only plans one step (or a few steps) ahead based on the information about the environment acquired by the sensor(s) mounted on the robot. Determining where the robot moves next can be a problematic task.
Over the last decade, a developmental shift has occurred from ground-based robot platforms to mobile aerial robots (e.g., UAV), as the latter provides more agility and speed. While outdoors, UAVs can easily navigate the airspace. However, navigating indoors requires development of a system for small UAVs to navigate in indoor environments (e.g., corridor, warehouses). In such settings, the next candidate positions to explore typically refer to where the open spaces (e.g., open doors) are. Thus, the problem is then reduced to finding open doorways in such an environment.
Many visual doorway detection algorithms have been proposed in the past, as it is of great importance for both navigation and manipulation tasks. Most of the earlier works focused on extracting two-dimensional (2D) appearance and shape features to recognize doors. For example, A. C. Murillo, J. Kosecka, J. J. Guerrero, and C. Sagues, in “Visual Door Detection Integrating Appearance and Shape Cues”, Journal of Robotics and Autonomous Systems, 2008, proposed a probabilistic approach by defining the likelihood of generating the door configurations with various features. In other work, Zhichao Chen and Stanley Birchfield, in “Visual Detection of Lintel-Occluded Doors from a single image, Workshop on Visual Localization from Mobile Platforms, CVPR 2008, proposed a Adaboost based approach along with two geometric features, concavity and bottom-edge intensity, to model the door explicitly. In yet other work, Yingli Tian, Xiaodong Yang, and Aries Arditi, in “ComputerVision-based Door Detection for Accessibility of Unfamiliar Environments to Blind Persons,” ICCHP (2) 2010, further proposed a more generic geometric based approach to detect doors based on stable features such as edges and corners. However, as in most 2D vision algorithms, these works are sensitive to common factors such as illumination changes, occlusion, clutter, and perspective distortion.
As noted above, many approaches toward indoor robot navigation and exploration have been developed in the past. One of the major categories among these approaches focus on addressing the SLAM (Simultaneous Localization and Mapping) problem, where the goal is to integrate the information collected during navigation into an accurate map possible. In other words, SLAM aims to localize the robot and reconstruct the map from its trajectory. Many recent works in this category has started to utilize 3D range sensor in conjunction with point cloud alignment mechanisms for autonomous UAV navigation. An example of such work is that by Shaojie Shen, Nathan Michael, and Vijay Kumar, in “Autonomous Multi-Floor Indoor Navigation with a Computationally Constrained MAV”, ICRA 2011. However, this line of work does not address the important question of where the robot should go next.
Another related area falls into obstacle avoidance. Due to the growing interests in smaller UAV flying in indoor and other GPS denied environments, quite a few research works have been developed to utilize onboard visual sensors to ensure safe maneuver in such conditions. Techniques focusing on monocular sensors have long been the main studied area. This includes the optical flow based approach by Zigg et al. (i.e., Simon Zigg, Davide Scaramuzza, Stephan Weiss, Roland Siegwart, “MAV Navigation through Indoor Corridors Using Optical Flow”, ICRA 2010) and the imitation learning based approach by Ross (i.e., Stephane Ross et al., “Learning Monocular Reactive UAV Control in Cluttered Natural Environments”, CoRR abs/1211.1690, 2012). Similar to the SLAM community, researchers also started to investigate the areas of utilizing Lidar or other RGB-D sensors for obstacle avoidance (e.g., Allen Ferrick, Jesse Fish, Edward Venator, Gregory S. Lee, “UAV Obstacle Avoidance Using image Processing Techniques”, Technologies for Practical Robot Applications, 2012). However, regardless of monocular vision or 3D vision, a common theme across most works on obstacle avoidance is the reactive action control for UAVs. This means that the control system will react and prevent the UAV from colliding with an obstacle when it is close by. However, it does not plan ahead for opportunity spaces which are further away to be explored.
In Lange's work (i.e., Sven Lange, Niko Sunderhauf Peer Neubert, Sebastian Drews, Peter Protzel, “Autonomous Corridor Flight of a UAV Using a Low-Cost and Light-Weight RGB-D Camera”, Advances in Autonomous Mini Robots, 2012), a 3D algorithm is proposed to process a point cloud captured by a Kinect sensor mounted on a UAV. The UAV is assumed to navigate and explore in an indoor corridor environment. The algorithm simply detects 4 major planes from the point cloud: two walls, a ground and a ceiling. Then, the distances between the UAV and each of the four planes are computed. Subsequently, the position of the UAV is adjusted and maintained in the center of the four planes. This implementation is very straight forward in a corridor setting. While the system of Lange allows the UAV to move in straight line, it does not extend beyond that in that it does not identify the exact location and orientation of open doors which are suitable for navigation.
Another related work is that of Derry et al. (i.e., Matthew Derry, Brenna Argall, “Automated Doorway Detection for Assistive Shared-Control Wheelchairs”, ICRA 2013), in which a 3D based algorithm is proposed to detect doors for assistive wheelchairs. The work of Lange is not appropriate for a UAV in that it operates on a ground plane and also imposes strong assumptions on the geometry of the point cloud (e.g., the input point cloud contains mostly front facing walls, the viewing angle between the sensor and a wall is unchanged in y-axis etc.).
Thus, a continuing need exists for a system that provides fast and efficient detection of open doorways using only 3D point cloud data and, in doing so, provides detection of the location and orientation of doorways through which an autonomous UAV can navigate.